package com.phy.kim.Leetcode;

/**
 * @Author: RiceDoggyRoll
 * @Date: 2021/11/21 23:33
 * @Description: 给定一个含有n个正整数的数组和一个正整数 target 。
 * <p>
 * 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组[numsl, numsl+1, ..., numsr-1, numsr] ， 并返回其长度。 如果不存在符合条件的子数组，返回
 * 0 。
 */
public class Leetcode0209MinSubArrayLen {

  /**
   * 看到连续子串，首先想到滑动窗口： 初始状态下，start 和 end 都指向下标 00，{sum}sum 的值为 00。
   * <p>
   * 每一轮迭代，将 nums[end] 加到 sum，如果 sum≥target，则更新子数组的最小长度（此时子数组的长度是 end−start+1），然后将 nums[start] 从 sum
   * 中减去并将 start 右移，直到sum<s， 在此过程中同样更新子数组的最小长度。在每一轮迭代的最后，将 end 右移。
   */

  public int minSubArrayLen(int target, int[] nums) {
    int n = nums.length;
    if (n == 0) {
      return 0;
    }
    int left = 0;
    int sum = 0;
    int ans = Integer.MAX_VALUE;
    for (int right = 0; right < n; right++) {
      sum += nums[right];
      while (sum >= target){
        ans = Math.min(ans, right-left+1);
        sum -=nums[left++];
      }
    }
    return ans > n ? 0 : ans;
  }
}
